package leetcode; /**
 * description:
 * author:zt
 * date:2021-07-30
 */

import java.util.HashMap;
import java.util.LinkedList;

/**
 * 给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。
 *
 * 每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
 */
public class leetcode662_2 {
    public int widthOfBinaryTree(TreeNode root) {
        //记录每一个节点和他所在的层数
        HashMap<TreeNode, Integer> map = new HashMap<>();
        //用队列来辅助实现广度优先搜索 按行遍历
        LinkedList<TreeNode> queue = new LinkedList<>();
        int currentLevel = 1;
        int currentLevelNodes = 0;
        int ans = Integer.MIN_VALUE;
        queue.add(root);
        map.put(root,currentLevel);

        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            if (currentLevel == map.get(node)) currentLevelNodes ++;
            else{
                ans = Math.max(ans,currentLevelNodes);
                //走到下一行的首个节点 进行此操作
                currentLevel++;
                currentLevelNodes = 1;
            }
            if (node.left!=null){
                map.put(node.left,currentLevel+1);
                queue.add(node.left);
            }
            if (node.right!=null){
                map.put(node.right,currentLevel+1);
                queue.add(node.right);
            }
        }
        return ans;
    }
}
